1. Field of the Invention
The present invention relates to a group signature system, an apparatus and a storage medium, and more particularly, it relates to a group signature system, an apparatus and a storage medium which can decrease a calculation amount to improve a calculation speed.
2. Description of the Related Art
A group signature system in which electronic signatures have anonymity was suggested by Chaum et al. in 1991. In a usual electronic signature system, a public key for verifying a signature corresponds to a private key for generating the signature in a relation of one to one, and hence the anonymity of a signature generator cannot be kept.
On the other hand, in the group signature system, a group public key for verifying the signature corresponds to member private keys for generating the signatures in a relation of one to n, and hence the anonymities of signature generators are kept. That is, in the group signature system, one group public key corresponds to n member private keys, and in consequence, the signature generator cannot be specified at a time of the signature verification owing to its properties. Moreover, the group signature system has properties such that only a group administrator who is a privileged person can specify a signer.
In an initial group signature system, however, the length of the signature or a calculation amount for generating the signature is proportional to the number of members. Therefore, the system has a very poor efficiency for a group including a large number of members, and is thus not suitable for a realization.
Meanwhile, a group signature system whose efficiency which does not depend on the number of members was suggested by Camenisch et al. in 1997. In this system, the signature of a group administrator with respect to each member private key is used as a membership certificate. The group signature includes the membership certificate (or a portion thereof) encrypted by the public key of the group administrator, and a non-interactive knowledge proof indicating that the membership certificate is correctly encrypted and the member private key and the membership certificate are held. A signature verifier can verify the signature of the member by the verification of the non-interactive knowledge proof. Furthermore, the group administrator can specify a signer by decrypting the membership certificate. The concept of using such a membership certificate is the key basis for the subsequent group signature systems.
However, in the system of Camenisch et al., the efficiency does not depend on the number of the members, but the efficiency is poor from a practical viewpoint.
The first practical group signature system is a system suggested by Ateniese et al. in 2000 (hereinafter referred to as the [ACJT00] system). The Ateniese group signature system has a noticeably enhanced efficiency, and can accordingly be investigated to be put to practical use. The Ateniese group signature system requires a calculation amount about 200 times that of RSA signature generation during signature generation, and hence the improvement thereof is continued to be investigated. The security of the Ateniese system builds on the strong-RSA problem.
At present, three high speed group signature systems are known, as follows. One of them is a system suggested by Camenisch et al. in 2004 (e.g., see J. Camenisch and J. Groth, “Group Signatures: Better Efficiency and New Theoretical Aspects”, Forth Int. Conf. on Security in Communication Networks—SCN 2004, LNCS 3352, pp. 120 to 133, 2005. This will hereinafter be referred to as the [CG04] system. The full paper can be acquired from the URL http://www.brics.dk/˜jg/ (as of March 2008)). The signature generating calculation amount of the [CG04] system is decreased to be about eight times that of RSA signature generation. The security of the [CG04] system also builds on the strong-RSA problem. The second is a system suggested by Furukawa et al. in 2005 (e.g., see J. Furukawa and H. Imai, “An Efficient Group Signature Scheme from Bilinear Maps”, ACISP 2005, LNCS 3574, pp. 455 to 467, 2005. This will hereinafter be referred to as the [FI05] system). The third is a system suggested by Delerablee et al. (e.g., see C. Delerablee and D. Pointcheval, “Dynamic Fully Anonymous Short Group Signatures”, VIETCRYPT, LNCS 4341, pp. 193 to 210, 2006. This will hereinafter be referred to as the [DP06] system). The [FI05] and [DP06] systems utilize a bilinear image, and the security of each system builds on a presumption in a bilinear group.
Improvements have been made to the speed and the functions of the group signature system, a key function of which is the revocation function. Revocation is a key function for canceling memberships from services or forcibly eliminating illegal memberships, when developing the services utilizing group signatures. Each of the above [CG04], [FI05] and [DP06] systems has the revocation function.
As a method for realizing a higher security and flexible group administration, there has been investigated a system which can vary confidential information to be handled for each group administrating function to divide authorities. Specifically, there is considered a system where functions of generating a member private key, specifying signers and revoking the signers, respectively, which have heretofore been performed all by a group administrator, are divided by a member private key generator, a signer specifier and a revocation administrator in charge.
Moreover, a property referred to as non-frameability is also suggested in which a verifier can confirm that the signer is appropriately specified by the group administrator or the signer specifier.
Furthermore, a property referred to as self-traceability is also suggested in which it can be proved with respect to the verifier that a certain signature is generated by the signer only when this is desired by the signer.